[Day 15] Custom encryption

2024 iThome 鐵人賽

DAY 15

Security

picoCTF系列第 15 篇

16th鐵人賽

2024-09-14 00:13:55

397 瀏覽

分享至

看到題目，可以知道目標是要把 flag_info 解密，並且 code file 可以讓我們分析如何得到 flag。而提示告訴我們，要了解這題是如何加密的。

hint 1：Understanding encryption algorithm to come up with decryption algorithm.

將題目所給的檔案下載，發現有一個 python 檔和一個文字檔。

$ ls 
custom_encryption.py  enc_flag

執行兩個檔案，會發現 python 檔無法執行，enc_flag 中則是出現一個陣列和變數 a 和 b。

$ chmod +x custom_encryption.py 
$ python3 custom_encryption.py 
Traceback (most recent call last):
  File "custom_encryption.py", line 63, in <module>
    message = sys.argv[1]
IndexError: list index out of range
$ cat enc_flag 
a = 94
b = 29
cipher is: [260307, 491691, 491691, 2487378, 2516301, 0, 1966764, 1879995, 1995687, 1214766, 0, 2400609, 607383, 144615, 1966764, 0, 636306, 2487378, 28923, 1793226, 694152, 780921, 173538, 173538, 491691, 173538, 751998, 1475073, 925536, 1417227, 751998, 202461, 347076, 491691]

打開 python 檔，以下是完整的 code。

from random import randint
import sys

def generator(g, x, p):
    return pow(g, x) % p

def encrypt(plaintext, key):
    cipher = []
    for char in plaintext:
        cipher.append(((ord(char) * key*311)))
    return cipher

def is_prime(p):
    v = 0
    for i in range(2, p + 1):
        if p % i == 0:
            v = v + 1
    if v > 1:
        return False
    else:
        return True

def dynamic_xor_encrypt(plaintext, text_key):
    cipher_text = ""
    key_length = len(text_key)
    for i, char in enumerate(plaintext[::-1]):
        key_char = text_key[i % key_length]
        encrypted_char = chr(ord(char) ^ ord(key_char))
        cipher_text += encrypted_char
    return cipher_text

def test(plain_text, text_key):
    p = 97
    g = 31
    if not is_prime(p) and not is_prime(g):
        print("Enter prime numbers")
        return
    a = randint(p-10, p)
    b = randint(g-10, g)
    print(f"a = {a}")
    print(f"b = {b}")
    u = generator(g, a, p)
    v = generator(g, b, p)
    key = generator(v, a, p)
    b_key = generator(u, b, p)
    shared_key = None
    if key == b_key:
        shared_key = key
    else:
        print("Invalid key")
        return
    semi_cipher = dynamic_xor_encrypt(plain_text, text_key)
    cipher = encrypt(semi_cipher, shared_key)
    print(f'cipher is: {cipher}')

if __name__ == "__main__":
    message = sys.argv[1]
    test(message, "trudeau")

接著我們一一來看每個函式。

從 main 知道，首先會呼叫 test 這個函式， message 和 "trudeau" 會傳遞到 test() 中。
我們能知道：plain_text = message; text_key = "trudeau"。

if __name__ == "__main__":
    message = sys.argv[1]
    test(message, "trudeau")

接著看到 test 函式，得知 p = 97, g = 31，並且知道這個函式裡主要進行了三個部分：

(1) 確認 key ?= b_key，若等於，則繼續 (2) 找到 semi_cipher，找到後再進行 (3) 找到 cipher。

def test(plain_text, text_key):
    p = 97
    g = 31
    if not is_prime(p) and not is_prime(g):
        print("Enter prime numbers")
        return
    a = randint(p-10, p)
    b = randint(g-10, g)
    print(f"a = {a}")
    print(f"b = {b}")
    u = generator(g, a, p)
    v = generator(g, b, p)
    key = generator(v, a, p)
    b_key = generator(u, b, p)
    shared_key = None
    if key == b_key:
        shared_key = key
    else:
        print("Invalid key")
        return
    semi_cipher = dynamic_xor_encrypt(plain_text, text_key)
    cipher = encrypt(semi_cipher, shared_key)
    print(f'cipher is: {cipher}')

接著來仔細說明三個部分。

(1) 要確定 key = b_key，需要看到 generator 函式，以及 test 的前半段。

def generator(g, x, p):
    return pow(g, x) % p
    
def test(plain_text, text_key):
    p = 97
    g = 31
    if not is_prime(p) and not is_prime(g):
        print("Enter prime numbers")
        return
    a = randint(p-10, p)
    b = randint(g-10, g)
    print(f"a = {a}")
    print(f"b = {b}")
    u = generator(g, a, p)
    v = generator(g, b, p)
    key = generator(v, a, p)
    b_key = generator(u, b, p)
    shared_key = None
    if key == b_key:
        shared_key = key
    else:
        print("Invalid key")
        return

根據以上 code 還有 enc_flag 中定義的 a 和 b，我們使用 python 來驗證 key 是否等於 b_key。

>>> g = 31; p = 97; a = 94; b = 29;
>>> u = pow(g,a)%p
>>> v = pow(g,b)%p
>>> key = pow(v,a)%p
>>> b_key = pow(u,b)%p
>>> print(key,b_key)
93 93

從程式碼結果，可以確定 pow( v, a ) % p = pow( u, b ) % p = 93，於是進行第 2 個部分。

(2) 接著再看到 semi_cipher 這個變數，需要呼叫到 dynamic_xor_encrypt 這個函式。

def dynamic_xor_encrypt(plaintext, text_key):
    cipher_text = ""
    key_length = len(text_key)
    for i, char in enumerate(plaintext[::-1]):
        key_char = text_key[i % key_length]
        encrypted_char = chr(ord(char) ^ ord(key_char))
        cipher_text += encrypted_char
    return cipher_text
    
    
def test(plain_text, text_key):
	  ......
    semi_cipher = dynamic_xor_encrypt(plain_text, text_key)
    cipher = encrypt(semi_cipher, shared_key)
    print(f'cipher is: {cipher}')

看到 dynamic_xor_encrypt() 函式，我們不知道其中 plaintext 是甚麼，僅知

text_key = "trudeau”，key_length = 7
0≤ i ≤ 33 ( 因為加密和解密後的字串長度應該相等，這題 cipher list 長度是 34 )，
plaintext 會被從字串最尾端，從尾到頭加密。
key_char 會等於 "trudeau” 其中的一個字元 (會等於哪個字元要根據目前是第幾次的 iteration )，
encrypted_char 是由 char 的 ascii 值 xor key_char 的 ascii 值轉換而成。

先記住我們目前得到的資訊，然後繼續看下去，試著從結果回推。

(3) 看到 encrypt 函式。

def encrypt(plaintext, key):
    cipher = []
    for char in plaintext:
        cipher.append(((ord(char) * key*311)))
    return cipher

def test(plain_text, text_key):
	  ......
    cipher = encrypt(semi_cipher, shared_key)
    print(f'cipher is: {cipher}')

目前我們已知道 key = 93，也知道 cipher 後的值 list 是 [260307, 491691, 491691, 2487378, 2516301, 0, 1966764, 1879995, 1995687, 1214706, 0, 2400609, 607383, 144615, 1966764, 0, 636306, 2487378, 28923, 1793226, 694152, 780921, 173538, 173538, 491691, 173538, 751998, 1475073, 925536, 1417227, 751998, 202461, 347076, 491691]。

於是，可以由 key 和 cipher 回推 semi_cipher ( 如下程式碼所示 )，得到 semicipher = [9, 17, 17, 86, 87, 0, 68, 65, 69, 42, 0, 83, 21, 5, 68, 0, 22, 86, 1, 62, 24, 27, 6, 6, 17, 6, 26, 51, 32, 49, 26, 7, 12, 17]

>>> cipher = [260307, 491691, 491691, 2487378, 2516301, 0, 1966764, 1879995, 1995687, 1214766, 0, 2400609, 607383, 144615, 1966764, 0, 636306, 2487378, 28923, 1793226, 694152, 780921, 173538, 173538, 491691, 173538, 751998, 1475073, 925536, 1417227, 751998, 202461, 347076, 491691]
>>> semicipher = []
>>> for i in cipher: semicipher.append(int(i/311/93))
... 
>>> semicipher
[9, 17, 17, 86, 87, 0, 68, 65, 69, 42, 0, 83, 21, 5, 68, 0, 22, 86, 1, 62, 24, 27, 6, 6, 17, 6, 26, 51, 32, 49, 26, 7, 12, 17]

繼續回推，已知 text_key = ‘trudeau’ ，並且會循環使用 text_key 中的字元來進行加密和解密操作 ( 從第 0 個字元到第 6 個字元循環使用 )。

並且我們知道 XOR 兩次之後會得到原始資訊，也就是將加密過後的 ascii 再次 xor ord(key_char) 會得到 plaintext 的 ascii，於是可以得到以下 code。

>>> plaintext = ""
>>> text_key = "trudeau"
>>> key_length = len(text_key)
>>> for i, j in enumerate(semicipher):
...     key_char = text_key[i%key_length]
...     decrypt_text_rev = j ^ ord(key_char)
...     plaintext += chr(decrypt_text_rev)

最後，再把 plaintext reverse，就會得到 flag。

>>> print(plaintext[::-1])
picoCTF{custom_d2cr0pt6d_751a22dc}

完整的 solution code 如下：

cipher = [260307, 491691, 491691, 2487378, 2516301, 0, 1966764, 1879995, 1995687, 1214766, 0, 2400609, 607383, 144615, 1966764, 0, 636306, 2487378, 28923, 1793226, 694152, 780921, 173538, 173538, 491691, 173538, 751998, 1475073, 925536, 1417227, 751998, 202461, 347076, 491691]
semicipher = []
plaintext = ""
text_key = "trudeau"
key_length = len(text_key)

for i in cipher: semicipher.append(int(i/311/93))

for i, j in enumerate(semicipher):
	key_char = text_key[i%key_length]
	decrypt_text_rev = j ^ ord(key_char)
	plaintext += chr(decrypt_text_rev)

print(plaintext[::-1])